On va procéder par contradiction, en supposant que la somme est nulle (\(M_n(i,j)\in\{0,1\}\)).

Dans ce cas, aucune arête du maximal matching n'est adjacent à \(i\) ou à \(j\).

On peut donc ajouter l'arête \((i,j)\), ce qui amène à une contradiction puisque le matching est supposé maximal.

On note \(\mathcal T\) l'ensemble des triplets de points, \(Z_t\) l'indicatrice d'existence du triangle du triplet \(t\) et \(X\) la somme des \(Z_t\).

On majore la probabilité qu'un triangle existe via l'Inégalité de Markov.

Développer l'espérance par linéarité.

Dénombrement des triangles possibles.
$$=\binom n3p^3$$

Majoration via les données de l'énoncé + conclusion.

Utiliser l'Inégalité de Bienaymé-Tchebychev pour majorer \({\Bbb P}(X=0)\) (quand le décalage est majoré par l'espérance).

Il faut calculer la variance, et pour cela il nous faut la covariance.

Pour cela, on décompose \(Z_t\) en un produit de trois indicatrices, indiquant si une arête est présente.

Si les deux triangles ont un seul sommet commun (donc \(0\) arête), alors la covariance est nulle.

Pour \(t\) fixé, la somme des covariances de \(Z_t\) avec \(t\) fixé est donc égale à la variance de \(Z_t\), plus la somme des covariances avec les triangles qui ont plus de deux sommets en commun.

La variance de \(Z_t\) est facile à calculer (loi de Bernoulli), et dans la somme, chaque terme est égal.

La covariance peut être calculée en prenant la formule \({\Bbb E}[X_1X_2]-{\Bbb E}[X_1]{\Bbb E}[X_2]\) et en passant par les \(\xi_{ij}\).

Majoration en prenant uniquement les termes positifs.

La variance totale est obtenue en multipliant par le nombre de triangles possibles.

Reste à majorer et à prendre des équivalents pour conclure.

On va utiliser le Théorème de Stein-Chen, donc la plupart des hypothèses sont déjà vérifiées.

Reste à définir les variables de l'hypothèse, qu'on prend comme produit de deux \(\xi_{ij}\).

Calculer le terme de la majoration pour vérifier qu'il est fini.

On a alors la majoration par un terme qui tend vers \(0\).

Conclusion : la probabilité limite est obtenue via une loi de Poisson.

On passe par la fonctions génératrice du vecteur entier.

On conditionne par \(Z\) dans l'espérance.

Dans cette espérance conditionnelle, on peut remplacer \(z_i\) par une somme (avec des indicatrices, seul un terme est nul), et remplacer la puissance \(Y_i\) par un produit indexé sur \(Z\).

Chaque terme du produit est égal à la moyenne de \(z_i\), donc le tout revient à l'élever à la puissance \(Z\).

On peut calculer cette espérance par théorème de transfert et pas développement en série entière de l'exponentielle.

Elle peut être réécrite en un produit où chaque terme dépend d'un seul \(z_i\), et on reconnaît la fonction génératrice de \(\mathcal{Pois}(\lambda)\) en écrivant ce produit.

Identification simple.

Le problème est devenu un problème d'Optimisation sous contraintes mixtes d'égalité et d'inégalité.

On résout ce problème en passant par le lagrangien.

Cela peut être modélisé via une EDO.

On recherche un point stationnaire, i.e. Un point où la dérivée s'annule.

Pour étudier la convergence, on peut regarder la dérivée du carré de la norme.

Ecrire la transformée de Laplace de \(N_k\) pour des fonctions positives à support compact inclus dans \([0,t]\).

Développer \(N_n(f_n)\) par définition.

Transformer la somme d'indicatrices à l'exponent en somme de probabilités.

On reconnaît la transformée de Laplace de \(N(g)\) pour une certaine fonction \(g\).

C'est la transformée de Laplace d'un processus de Poisson, donc on a une expression alternative.

C'est de la forme de la transformée de Laplace de processus de Poisson indépendants, ce qui nous permet de conclure par caractérisation.

C'est un processus dans \({\Bbb R}^2\), qu'on va noter \(\hat N\).

Poser une fonction \(\phi:{\Bbb R}^2_+\to{\Bbb R}_+\) à support compact inclus dans \([a,b]\times[c,d]\).

On a la loi du nombre \(X\) de points \(T_n\) dans l'intervalle, et leur distribution connaissant \(X\).

On en déduit la transformée de Laplace de \(\hat N\) pour \(\phi\) (en prenant une densité inconnue \(f\) pour \(\sigma_n\)).

Remettre sous la forme de la transformée de Laplace d'un processus de Poisson.

Développer par définition du processus ponctuel.
$$={\Bbb E}\left[ e^{-\sum_{n\gt 0}\phi(T_n,\sigma_n)}\right]$$

Conditionner par rapport au \(X\) de points \(T_n\) dans \([a,b]\) \(\to\) on peut passer sous forme intégrale par théorème de transfert et par indépendance.
$$={\Bbb E}\left[{\Bbb E}\left[ {\prod^X_{n=1}\int^b_a\int^d_c\frac1{b-a}e^{-\phi(x,y)}f(y)\,dx\,dy}\,\middle|\,X\right]\right]$$

Passer par une somme d'indicatrices \(\Bbb 1_{X=k}\) pour simplifier l'expression.
$$={\Bbb E}\left[{\Bbb E}\left[ \sum ^{+\infty}_{k=1}\Bbb 1_{X=k}\prod^k_{n=1}{\int^b_a\int^d_c\frac1{b-a}e^{-\phi(x,y)}f(y)\,dx\,dy}\,\middle|\,X\right]\right]$$

Chaque terme dans la somme à l'exposant est identique \(\to\) on peut passer à la puissance \(k\).
$$={\Bbb E}\left[{\Bbb E}\left[ \sum ^{+\infty}_{k=1}\Bbb 1_{X=k}\left({\int^b_a\int^d_c\frac1{b-a}e^{-\phi(x,y)}f(y)\,dx\,dy}\right)^k\,\middle|\,X\right]\right]$$

Reste à calculer l'espérance des indicatrices (via la connaissance de la loi de \(X\).

$$=\sum ^{+\infty}_{k=1}e^{-\lambda(b-a)}\frac{(\lambda(b-a))^k}{k!}\left({\int^b_a\int^d_c\frac1{b-a}e^{-\phi(x,y)}f(y)\,dx\,dy}\right)^k$$

Reconnaître la série entière de l'exponentielle.
$$=\exp\left(-\lambda(b-a)+\lambda\int^b_a\int_c^de^{-\phi(x,y)}f(y)\,dx\,dy\right)$$

Remplacer \(b-a=\int^b_a\,dx\) et factoriser.
$$\begin{align}&=\exp\left(-\lambda\int^b_a\,dx+\lambda\int^b_a\int_c^de^{-\phi(x,y)}f(y)\,dx\,dy\right)\\ &=\exp\left(-\lambda\int^b_a\int^d_c(1-e^{-\phi(x,y)})\,f(y)\,dx\,dy\right)\end{align}$$

Etendre les domaines des intégrales via le domaine de \(\phi\).

$$=\exp\left(-\lambda\iint_{{\Bbb R}_+^2}(1-e^{-\phi(x,y)})f(y)\,dx\,dy\right)$$

On reconnaît \(\hat N(C_t)\), avec \(C_t\) un ensemble particulier de \({\Bbb R}^2_+\).

On a donc la loi de \(X_t\) d'après le cours (en intégrant sur \(C_t\)).

Ramener l'intégrale à \({\Bbb R}^2\) via une indicatrice.
$$\iint_{C_t}\lambda f(y)\,dx\,dy=\iint_{{\Bbb R}^2_+}\lambda f(y)\Bbb 1_{x\leqslant t\lt x+y}\,dx\,dy$$

Isoler l'indicatrice (intégrale en \(x\) et calculer son intégrale via la mesure de l'ensemble indiqué) ⚠ on est dans \({\Bbb R}_+\) !
$$=\int_{{\Bbb R}_+}\lambda f(y)\left(\int_{{\Bbb R}_+}\Bbb 1_{x\leqslant t\lt x+y}\,dx\right)\,dy$$
\(x\leqslant t\leqslant x+y\iff x\in[\max(t-y,0),t]\).
La mesure de cet ensemble est \(t-\min(t-y,0)=\min(y,t)\), ce qui nous donne : $$=\int_{{\Bbb R}_+}\lambda f(y)\min(y,t)\,dy$$

On reconnaît une espérance (seule façon de conclure, puisque \(f\) est la densité d'une loi inconnue).

$$={\Bbb E}[\min(\sigma_n,t)]$$

On sépare \(C_t\cup C_{t+s}\) en parties disjointes.

Par indépendance de chaque zone, la covariance se simplifie en une variance.

Puisque c'est une loi de Poisson, cette variance est égale à l'espérance.

Ecrire cette espérance sous forme intégrale en délimitant \(\hat N(U)\) par des indicatrices.

On peut calculer les intégrales et reconnaître une espérance pour conclure.

Un raisonnement rapide nous donne la propriété de Markov.

Le nombre d'infectés ne peut qu'augmenter, et la probabilité qu'il augmente de \(2\) d'un coup est très faible, donc la seule probabilité de transition non nulle est \(+1\).

Calculer cette probabilité de transition en passant par la formule avec \(\displaystyle{\lim_{h\to0} }\).

Cette quantité est donnée par la somme des temps de séjour dans tous les états sauf le dernier.

Ecrire la somme des inverses des \(q_{x,x+1}\).
$${\Bbb E}[T]=\sum_{x=1}^{n-1}\frac{n-1}{2\lambda x(n-x)}=\frac{n-1}{2\lambda}\sum_{x=1}^{n-1}\frac1{x(n-x)}$$

Faire un double théorème belge pour simplifier le terme principal (ou décomposition en fractions rationnelles).
$$\frac1{x(n-x)}=\frac Ax+\frac B{n-x}\implies (A,B)=\left(\frac1n,\frac1n\right)$$$\({\Bbb E}[T]=\frac{n-1}{2\lambda n}\sum_{x=1}^{n-1}\frac1x+\frac1{n-x}\)$

Les termes sont symétriques, donc on peut simplifier la somme.

$$=\frac{n-1}{\lambda n}\sum^{n-1}_{x=1}\frac1x=\frac{n-1}{\lambda n}H(n-1)$$

Les taux d'infection deviennent alors \(\lambda x\).

Il ne reste plus qu'à calculer la somme des inverses et à comparer avec la question précédente.

Faire le calcul pour un graphe simple.

Conclure par linéarité du laplacien.

Propriété du cours.

Il faut que la masse totale soit finie \(\to\) établir un critère.

C'est un problème d'optimisation sous contraintes.

Ecrire la relation de réversibilité.

Factoriser.

Faire la récurrence, en initialisant \(\pi_0=1\).

Pour montrer l'ergodicité, il faut montrer que le processus est sommable (par majoration), puisqu'on a l'ergodicité.

Checker la convergence des termes individuels et de la constante de normalisation \(\to\) ça tend vers une loi géométrique.

On reconnaît une chaîne de Markov classique.

Pour l'irréductibilité, montrer qu'on peut aller à \(0\) en venant de chaque état et qu'on peut aller à chaque état en partant de \(0\).

Dans le cas \(\gt 0\), alors en écrivant \(X_n\) en fonction de \(X_0\), on peut voir que \(X_n\overset{ps}{\underset{n\to+\infty}\longrightarrow}+\infty\), ce qui donne le caractère transitoire.

Dans l'autre cas, go Critère de Foster-Lyapounov pour l'ergodicité avec \(L(x)=\sum x_i^2\).

Déjà vu en cours.

Dans les notes de cours (\(I\) indépendantes files \(M/M/\infty/\infty\)).

Donner un équivalent de la probabilité qu'une arête existe (proba que l'une des flèches existe, moins proba que les deux existent en même temps).

Le résultat est alors l'un des résultats du cours.

On a par construction une loi binomiale.

Développer le terme de gauche en conséquence.

Dégager les termes inconnus.

Inégalité de convexité \(1+x\leqslant e^x\).

Exprimer \(\lvert S(i_0\to)\rvert\) à l'aide de \(\lvert A_t\rvert\).

On a une expression de \(\lvert A_t\rvert\), qu'on peut utiliser pour calculer \({\Bbb P}(\lvert S(i_0\to)\rvert\gt m)\).

Multiplier l'inégalité de \(2)\) pour tout \(t\) pour obtenir une majoration de \({\Bbb E}[e^{\theta(\lvert D_1\rvert+\dots+\lvert D_t\rvert)}]\).

On conclut en utilisant l'Inégalité de Markov, avec \(t\mapsto e^{\theta t}\).

La borne étant valable \(\forall\theta\gt 0\), on prend \(\theta=f(\lambda)\) fonction permettant d'optimiser la borne.

On prend l'union sur \(i_0\) en multipliant cette probabilité par \(n\) et on prend \(t\) tq la proba soit \(\leqslant\frac1n\).

Si on note \(X_t\) le nombre de clients dans le système à l'instant \(t\), les données sont quasiment dans l'énoncé.

Ecrire l'espérance de \(\frac C{2\lceil t^*\rceil}\) comme une intégrale de \({\Bbb P}(\cdot\gt x)\).

Majorer par une somme sur les entiers de cette proba (//méthode des rectangles).

Majorer chaque terme via la borne de la première, partie de la question (on peut faire le minimum avec \(1\) car c'est une probabilité).

La borne vient alors du calcul de cette série.

C'est donné par leur probabilité de transition, normalisées.